package com.lw.leetcode.sort;

/**
 * 归并排序
 *
 * @Author liw
 * @Version 1.0
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {1,0};
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int st, int end) {
        int m = (st + end) / 2;
        if (st < end) {
            mergeSort(arr, st, m);
            mergeSort(arr, m + 1, end);
            merge(arr, st, m, end);
        }
    }

    private static void merge(int[] arr, int st, int m, int end) {
        int[] temp = new int[(end - st) + 1];
        int l = st;
        int r = m + 1;
        int i = 0;
        while (l <= m && r <= end) {
            temp[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
        }
        while (l <= m) {
            temp[i++] = arr[l++];
        }
        while (r <= end) {
            temp[i++] = arr[r++];
        }
        System.arraycopy(temp, 0, arr, st, temp.length);
    }

}
